package leetcode.problems.P144二叉树的前序遍历;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class PreorderTraversal {
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// 1.递归
class Solution1 {
    private List<Integer> nodes;

    public List<Integer> preorderTraversal(TreeNode root) {
        nodes = new LinkedList<>();
        traversal(root);
        return nodes;
    }

    public void traversal(TreeNode root) {
        if (root != null) {
            nodes.add(root.val);
            traversal(root.left);
            traversal(root.right);
        }
    }
}

// 2.迭代
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> nodes = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                nodes.add(root.val);
                root = root.left;
            } else {
                root = stack.pop().right;
            }
        }
        return nodes;
    }
}